package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayList;
import java.util.List;

/**
 * 729. 我的日程安排表 I
 * 
 * https://leetcode.cn/problems/my-calendar-i/
 * 
 * @author jie.deng
 *
 */
class MyCalendar {

	private List<Integer> list;

	public MyCalendar() {
		list = new ArrayList<>();
	}

	public boolean book(int start, int end) {
		int idx = searchInsertIdx(start, this.list);
		if (idx % 2 == 1) {
			return false;
		}
		if (list.size() == idx) {
			list.add(start);
			list.add(end);
		} else {
			if (end > list.get(idx)) {
				return false;
			} else {
				list.add(idx, end);
				list.add(idx, start);
			}
		}
		return true;
	}

	private int searchInsertIdx(int num, List<Integer> list) {
		int left = 0;
		int right = list.size();
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (num < list.get(mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}

}